package com.lw.leetcode.stack.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * 909. 蛇梯棋
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/12 19:22
 */
public class SnakesAndLadders {

    public static void main(String[] args) {
        SnakesAndLadders test = new SnakesAndLadders();

        // 4
        int[][] arr = {{-1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}, {-1, 35, -1, -1, 13, -1}, {-1, -1, -1, -1, -1, -1}, {-1, 15, -1, -1, -1, -1}};

        // 1
//        int[][] arr =  {{-1,-1},{-1,3}};

        // -1
//        int[][] arr =  {{1,1,-1},{1,1,1},{-1,1,1}};

        int i = test.snakesAndLadders(arr);
        System.out.println(i);
    }

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int length = n * n;
        int[] arr = new int[length + 1];
        int[] flag = new int[length + 1];
        int index = 1;
        for (int i = n - 1; i >= 0; i--) {
            if ((n - i - 1) % 2 == 0) {
                for (int j = 0; j < n; j++) {
                    arr[index++] = board[i][j];
                }
            } else {
                for (int j = n - 1; j >= 0; j--) {
                    arr[index++] = board[i][j];
                }
            }
        }
        LinkedList<Integer> list1 = new LinkedList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        list1.addLast(1);
        board[0][0] = -2;
        int count = 1;
        int v = 0;
        while (v != length) {
            while (!list1.isEmpty()) {
                int k = list1.pollFirst();
                for (int i = 1; i <= 6; i++) {
                    if (k + i > length) {
                        continue;
                    }
                    v = k + i;
                    if (arr[k + i] != -1) {
                        v = arr[v];
                    }
                    if (v == length) {
                        return count;
                    }
                    if (flag[v] == 1) {
                        continue;
                    }
                    flag[v] = 1;
                    list2.addLast(v);
                }
            }
            if (list2.isEmpty()) {
                return -1;
            }
            while (!list2.isEmpty()) {
                list1.addLast(list2.poll());
            }
            count++;
        }
        return count;
    }


}
